from collections import deque

from com.example.leetcode.tree.common import TreeUtils
from com.example.leetcode.tree.common.TreeUtils import TreeNode


# class Codec:
#
#     def serialize(self, root):
#         return ",".join(self.to_pre_order(root))
#
#     def to_pre_order(self, root):
#         if not root:
#             return ["null"]
#         return [str(root.val)] + self.to_pre_order(root.left) + self.to_pre_order(root.right)
#
#     def deserialize(self, data):
#         node_iter = iter(data.split(","))
#         return self.from_pre_order(node_iter)
#
#     def from_pre_order(self, node_iter):
#         val = next(node_iter)
#         if val == "null":
#             return None
#         node = TreeNode(int(val))
#         node.left = self.from_pre_order(node_iter)
#         node.right = self.from_pre_order(node_iter)
#         return node


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "null"
        result = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")
        return ",".join(result)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == "null":
            return None

        ## 解析节点
        nodes = data.split(",")
        root = TreeNode(int(nodes[0]))
        queue = deque([root])
        i = 1
        while queue:
            ## 当前节点出队
            node = queue.popleft()
            ## 如果左子节点存在
            if nodes[i] != "null":
                ## 构造节点并入队
                node.left = TreeNode(int(nodes[i]))
                queue.append(node.left)
            i += 1
            ## 如果右子节点存在
            if nodes[i] != "null":
                ## 构造节点并入队
                node.right = TreeNode(int(nodes[i]))
                queue.append(node.right)
            i += 1
        return root


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))


if __name__ == '__main__':
    nums = [1, 2, 3, None, None, 4, 5]
    root = TreeUtils.generate_binary_tree(nums)
    ser = Codec()
    deser = Codec()
    ans = deser.deserialize(ser.serialize(root))
    TreeUtils.print_tree(ans)
